%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Elementary Cryptanalysis}
\label{ElementaryCryptanalysis}

The most direct attack on a cryptosystem is an {\em exhaustive key
search} attack.  The key size therefore provides a lower bound on
the security of a cryptosystem.  As an example we compare the key
sizes of several of the cryptosystems we have introduced so far.
We assume that the alphabet for each is the 26 character alphabet.

\begin{center}
\begin{minipage}[t]{10cm}
Substitution ciphers:\\
\mbox{\hspace{4mm}}
Simple substitution ciphers: $26!$\\
\mbox{\hspace{4mm}}
Affine substitution ciphers: $\varphi(26) \cdot 26 = 12 \cdot 26 = 312$\\
\mbox{\hspace{4mm}}
Translation substitution ciphers: $26$\\
Transposition ciphers:\\
\mbox{\hspace{4mm}}
Transposition ciphers (of block length $m$): $m!$\\
Enigma : \\
\mbox{\hspace{4mm}}
Rotor choices (3 of 5): 60\\
\mbox{\hspace{4mm}}
Rotor positions: $26^3 = 17576$\\
\mbox{\hspace{4mm}}
Plugboard settings: 105578918576\\
\mbox{\hspace{4mm}}
Total combinations: 111339304373506560
\end{minipage}
\end{center}

The size of the keyspace is a naive measure, but provides an upper
bound on the security of a cryptosystem.  This measure ignores any
structure, like character frequencies, which might remain intact
following encryption.

\section{Classification of Cryptanalytic Attacks}

We do not consider enumeration of all keys a valid cryptanalytic
attack, since no well-designed cryptosystem is susceptible to such
an approach.  The types of legitimate attacks which we consider can
be classified in three categories:
ciphertext-only attack,
known plaintext attack, and
chosen plaintext attack.

\subsection*{Ciphertext-only Attack}
The cryptanalyst intercepts one or more messages all encoded with
the same encryption algorithm.

\noindent{\bf Goal:}
Recover the original plaintext or plaintexts, to discover the
deciphering key or find an algorithm for deciphering subsequent
messages enciphered with the same key.

\subsection*{Known Plaintext Attack}
The cryptanalyst has access to not only the ciphertext, but also
the plaintext for one or more of the messages.

\noindent{\bf Goal:}
Recover the deciphering key or find an algorithm for deciphering
subsequent messages (or the remaining plaintext) enciphered which
use the same key.

\subsection*{Chosen Plaintext Attack}
The cryptanalyst has access to ciphertext for which he or she
specified he plaintext.

\noindent{\bf Goal:}
Recover the discover the deciphering key or find an algorithm for
deciphering subsequent messages enciphered with the same key.

\vspace{4mm}
For the remainder of the chapter we consider cryptanalytic techniques
employed against classical cryptosystems for ciphertext-only attacks.

\section{Cryptanalysis by Frequency Analysis}
%\begin{center}{\large\bf Frequency Analysis}\end{center}

Given a sample of an English language newspaper text (stripped of spaces,
punctuation and other extraneous characters) the following gives the
approximate percentage of occurrences of each character.
$$
\begin{array}{ccccccccccccccc}
\tA & \tB & \tC & \tD & \tE & \tF & \tG & \tH & \tI & \tJ & \tK & \tL & \tM \\
\hline
7.3 & 0.9 & 3.0 & 4.4 &  13 & 2.8 & 1.6 & 3.5 & 7.4 & 0.2 & 0.3 & 3.5 & 2.5 \\
\\
\tN & \tO & \tP & \tQ & \tR & \tS & \tT & \tU & \tV & \tW & \tX & \tY & \tZ \\
\hline
7.8 & 7.4 & 2.7 & 0.3 & 7.7 & 6.3 & 9.3 & 2.7 & 1.3 & 1.6 & 0.5 & 1.9 & 0.1 \\
\end{array}
$$
The relative frequencies can change according to subject matter
and style of writing, but it is still possible to pick out those
characters with a high frequency of occurrence and those which
are rare:

\begin{tabular}{llll}
{\bf High frequency:} & $\{\tE,\tI,\tO,\tA\}$ (vowels) &
{\bf Low frequency:}  & $\{\tJ,\tK,\tQ,\tX,\tZ\}$ \\
                      & $\{\tT,\tN,\tR,\tS\}$ (consonants) \\
\end{tabular}


\begin{center}{\large\bf Examples of Cryptanalysis}\end{center}

Let's begin with the substitution ciphertext constructed previously:

\begin{center}
\begin{minipage}[c]{12.5cm}
\begin{verbatim}
QWMMPQDVKUVFDTXJQVDBOPIDUHDQQUGDLAMWJGXBGURRBPBURMKULDVX
OOKUJUOVDJQDGBWHLDJQQMUODQUBIMWBOVWUVXPBUBIOKUBGXBGURROK
UJUOVDJQVPWMMDJOUQDVKDBVKDCDAQXEDFKXOKLPWBIQVKDQDOWJXVAP
TVKDQAQVDHXQURMKULDVXOOKUJUOVDJQVKDJDTPJDVKDVPVURBWHLDJP
TCDAQXQPTDBPJHPWQQXEDBDNDJVKDRDQQFDFXRRQDDVKUVQXHMRDQWLQ
VXVWVXPBXQNDJAQWQODMVXLRDVPOJAMVUBURAVXOUVVUOCQ
\end{verbatim}
\end{minipage}
\end{center}

We find the following character counts, scaled to that of a
1000 character input text.
$$
\begin{array}{crcrcr}
\tA & 24.0964 \\
\tB & 54.2169 \\
\tC & 9.0361 \\
\tD & 129.5181 \\
\tE & 6.0241 \\
\tF & 12.0482 \\
\tG & 18.0723 \\
\tH & 18.0723 \\
\tI & 12.0482 \\
\end{array}
\quad
\begin{array}{crcrcr}
\tJ & 54.2169 \\
\tK & 51.2048 \\
\tL & 24.0964 \\
\tM & 36.1446 \\
\tN & 6.0241 \\
\tO & 57.2289 \\
\tP & 45.1807 \\
\tQ & 96.3855 \\
\tR & 39.1566 \\
\end{array}
\quad
\begin{array}{crcrcr}
\tS & 0 \\
\tT & 15.0602 \\
\tU & 81.3253 \\
\tV & 99.3976 \\
\tW & 39.1566 \\
\tX & 57.2289 \\
\tY & 0 \\
\tZ & 0 \\
    &   \\
\end{array}
$$

The distributions look like a frequency preserving substitution cipher.
We guess that the enciphering takes $\tE \mapsto \tD$ and $\tT \mapsto
\tV$ or $\tT \mapsto \tQ$.
The most frequent characters are \tD, \tV, \tQ, \tV, \tU, \tO, \tJ,
\tK, \tB\ and \tE, \tN, \tS, \tY, \tZ\ are of lowest frequency.

Equating high frequency and low frequency characters, we might first
guess
$$
\{\tE,\tI,\tO,\tA,\tT,\tN,\tR,\tS\} \mapsto
\{\tD,\tV,\tQ,\tU,\tO,\tJ,\tK,\tB\}
$$
and
$$
\{\tJ,\tK,\tQ,\tX,\tZ\} \mapsto
\{\tE,\tN,\tS,\tY,\tZ\}
$$
How would you go about reconstructing the entire text?

%\begin{center}{\Large\bf MATH3024: Lecture 06}\end{center}

%\section{Cryptanalysis: Frequency Analysis}

\subsection*{Index of Coincidence}

In the 1920's William Friedman introduced the {\em index of coincidence}
as a measure of the variation of character frequencies in text from a
uniform distribution.   The index of coincidence of a text space (e.g.
that of all plaintext or ciphertext) is defined to be the probability
that two randomly chosen characters are equal.  In a language over an
alphabet of size $n$, suppose that $p_i$ is the probability of a random
character is the $i$-th character in a string of length $N$. Then, in
the limit as the string length $N$ goes to infinity, the index of
coincidence in that language is:
$$
\sum_{i=1}^n p_i^2.
$$
Over an alphabet of 26 characters, the coincidence index of random text is
$$
\sum_{i=1}^{26} (1/26)^2 = 1/26\ \isom\ 0.0385.
$$
For English text, the coincidence index is around $0.0661$.  For a
finite string of length $N$, we the index of coincidence is defined
to be:
$$
\frac{\sum_{i=1}^n n_i(n_i-1)}{N(N-1)},
$$
where $n_i$ is the number of occurrences of the $i$-th character in
the string.

%\section{Cryptanalysis: Recognizing Periodity}

\begin{theorem}
The expected index of coincidence of a ciphertext of length $N$,
output from a period $m$ cipher, which is defined by $m$ independent
substitutions ciphers at each position in arithmetic progression
the $i+jm$, is
$$
\frac{1}{m} \left(\frac{N-m}{N-1}\right) i_{\rX} +
\frac{(m-1)}{m} \left(\frac{N}{N-1}\right) i_n,
$$
where $i_{\rX}$ is the index of coincidence of the space $\rX$,
the size of the alphabet is $n$, and and $i_n = 1/n$ is the index
of coincidence of random text in that space.
\end{theorem}

\begin{example}
\label{example-Vigenere-1}
Consider the ciphertext enciphered with a Vigen\`ere cipher:
\begin{center}
\begin{minipage}[c]{12.5cm}
\begin{verbatim}
OOEXQGHXINMFRTRIFSSMZRWLYOWTTWTJIWMOBEDAXHVHSFTRIQKMENXZ
PNQWMCVEJTWJTOHTJXWYIFPSVIWEMNUVWHMCXZTCLFSCVNDLWTENUHSY
KVCTGMGYXSYELVAVLTZRVHRUHAGICKIVAHORLWSUNLGZECLSSSWJLSKO
GWVDXHDECLBBMYWXHFAOVUVHLWCSYEVVWCJGGQFFVEOAZTQHLONXGAHO
GDTERUEQDIDLLWCMLGZJLOEJTVLZKZAWRIFISUEWWLIXKWNISKLQZHKH
WHLIEIKZORSOLSUCHAZAIQACIEPIKIELPWHWEUQSKELCDDSKZRYVNDLW
TMNKLWSIFMFVHAPAZLNSRVTEDEMYOTDLQUEIIMEWEBJWRXSYEVLTRVGJ
KHYISCYCPWTTOEWANHDPWHWEPIKKODLKIEYRPDKAIWSGINZKZASDSKTI
TZPDPSOILWIERRVUIQLLHFRZKZADKCKLLEEHJLAWWVDWHFALOEOQW
\end{verbatim}
\end{minipage}
\end{center}
The coincidence index of this text is $0.0439$.  This would suggest a
period of approximately $5$.  We will see that this is a bad estimate.
Note that this doesn't disprove the theorem, it just shows that the
statistical errors are too great and that we would need a much larger
sample size to converge to this theoretical expectation, or that the
substitutions employed were not independent.
\end{example}

\noindent{\bf Exercise.}
Explain why ciphertext for a particular key need not follow the behavior
predicted by the theorem.

\subsection*{Decimation of Sequences}
For a sequence $S = s_1 s_2 s_3\dots$ and positive integers $m$
and $k$ such that $1 \le k \le m$, we denote the $k$-th decimation of
period $m$ as the sequence $s_{k} s_{m+k} s_{2m+k}\dots$.  If $S$ is
a ciphertext string (a sequence of characters in the alphabet $\cA'$)
enciphered by a cipher with period $m$, then the decimations of period
$m$ capture the structure of the cipher without periods.

\begin{example}
\label{example-Vigenere-2}
If we take the previous ciphertext and average the coincidence indices
of each of the $k$-the decimated sequences of period $m$, we find:
$$
\begin{array}{rc}
 m & {\rm{CI}} \\
\hline
 1 & 0.0439 \\
 2 & 0.0438 \\
 3 & 0.0435 \\
 4 & 0.0434 \\
 5 & 0.0421 \\
\end{array}
\quad
\begin{array}{rc}
 m & {\rm{CI}} \\
\hline
 6 & 0.0424 \\
 7 & 0.0442 \\
 8 & 0.0414 \\
 9 & 0.0438 \\
10 & 0.0407 \\
\end{array}
\quad
\begin{array}{rc}
 m & {\rm{CI}} \\
\hline
11 & 0.0653 \\
12 & 0.0408 \\
13 & 0.0445 \\
14 & 0.0418 \\
15 & 0.0423 \\
\end{array}
$$
From this table, the correct period, $11$, is obvious.
\end{example}

\noindent{\bf Exercise.}
What do you expect to see in such a table if the period is composite?
Hint: consider the period of the decimated sequence, and apply the
theorem.

\subsection*{Kasiski method}
The Prussian military officer Friedrich Kasiski made the following
observation on the Vigen\`ere cipher in 1863.  If a frequently
occurring pattern, such as {\tt THE} is aligned at the same position
with respect to the period, then the same three characters will appear
in the ciphertext, at a distance which is an exact multiple of $m$.
By looking for frequently occurring strings in the ciphertext, and
measuring the most frequent divisors of the displacements of these
strings, it is often possible to identify the period, hence to
reduce to a simple substitution.

\begin{example}
\label{example-Vigenere-3}
Returning to the ciphertext of Example~\ref{example-Vigenere-1}, we
find that the three substrings {\tt SYE}, {\tt ZKZ}, and {\tt KZA}
each occur three times.  The positions of these occurrences are:

\begin{center}
\begin{tabular}{cl}
{\tt SYE}: &  122, 196, 383 \\
{\tt ZKZ}: &  252, 439, 472 \\
{\tt KZA}: &  253, 440, 473 \\
\end{tabular}
\end {center}

Note that {\tt ZKZ} and {\tt KZA} are substrings of the four character
string {\tt ZKZA} appearing three times in the ciphertext!  Moreover two
of the occurrences of the string {\tt SYE} appear as substrings of the
longer string {\tt SYEV}.

Now we look for common divisors of the differences between the positions
of the frequently occurring substrings.
$$
\begin{array}{ll}
196-122 & = 2 \cdot 37 \\
383-196 & = 11 \cdot 17 \\
383-122 & = 3^2 \cdot 29
\end{array}
\quad
\begin{array}{ll}
439-252 & = 11 \cdot 17 \\
472-439 & = 3 \cdot 11 \\
472-252 & = 2^2 \cdot 5 \cdot 11
\end{array}
$$
We see that our guess of $11$ for the period appears as a divisor
of the distances between each of the occurrences of the common four
character substring, and divides one of the differences of the other
three string characters.
\end{example}

\noindent{\bf Exercise.}
If $11$ is the correct period, why does it not appear in all of the
differences above?  Which of the occurrences can be attributed as random?

\section{Breaking the Vigen\`ere Cipher}
\label{Vigenere-Cryptanalysis}

Now that we have established that the period is 11, we can write the
ciphertext in blocks and look at the strings which occur frequently at
the same position within blocks.

\begin{center}
\begin{tabular}{rcccc}
   &         1         &           2       &          3        &          4       \\
 1 & {\tt OOEXQGHXINM} & {\tt FRTRIFSSMZR} & {\tt WLYOWTTWTJI} & {\tt WMOBEDAXHVH} \\
 2 & {\tt SFTRIQKMENX} & {\tt ZPNQWMCVEJT} & {\tt WJTOHTJXWYI} & {\tt FPSVIWEMNUV} \\
 3 & {\tt WHMCXZTCLFS} & {\tt CVNDLWTENUH} & {\tt SYKVCTGMGYX} & {\tt SYELVAVLTZR} \\
 4 & {\tt VHRUHAGICKI} & {\tt VAHORLWSUNL} & {\tt GZECLSSSWJL} & {\tt SKOGWVDXHDE} \\
 5 & {\tt CLBBMYWXHFA} & {\tt OVUVHLWCSYE} & {\tt VVWCJGGQFFV} & {\tt EOAZTQHLONX} \\
 6 & {\tt GAHOGDTERUE} & {\tt QDIDLLWCMLG} & {\tt ZJLOEJTVLZK} & {\tt ZAWRIFISUEW} \\
 7 & {\tt WLIXKWNISKL} & {\tt QZHKHWHLIEI} & {\tt KZORSOLSUCH} & {\tt AZAIQACIEPI} \\
 8 & {\tt KIELPWHWEUQ} & {\tt SKELCDDSKZR} & {\tt YVNDLWTMNKL} & {\tt WSIFMFVHAPA} \\
 9 & {\tt ZLNSRVTEDEM} & {\tt YOTDLQUEIIM} & {\tt EWEBJWRXSYE} & {\tt VLTRVGJKHYI} \\
10 & {\tt SCYCPWTTOEW} & {\tt ANHDPWHWEPI} & {\tt KKODLKIEYRP} & {\tt DKAIWSGINZK} \\
11 & {\tt ZASDSKTITZP} & {\tt DPSOILWIERR} & {\tt VUIQLLHFRZK} & {\tt ZADKCKLLEEH} \\
12 & {\tt JLAWWVDWHFA} & {\tt LOEOQW} \mbox{\hspace{10mm}}
\end{tabular}
\end{center}

Some of the longer strings which appear more than one at distances which
are a multiple of 11 are given in the following table. The first column
indicates the number of times the full string appears.

\begin{center}
\begin{tabular}{r|c|c|c|c|c|c|c|c|c|c|c}
 \#  &   1  &  2   &  3  &  4  &  5  &  6  &  7  &  8  &  9  &  10 &  11 \\ \hline
  3  &  \tZ & \tA  &     &     &     &     &     &     &     & \tZ & \tK \\ \hline
  2  &      &      & \tN & \tD & \tL & \tW & \tT &     &     &     &     \\ \hline
  2  &      &      &     & \tP & \tW & \tH & \tW & \tE &     &     &     \\ \hline
  2  &  \tV &      &     &     &     &     &     &     & \tS & \tY & \tE \\ \hline
  2  &      &      &     &     &     & \tL & \tW & \tC &     &     &     \\ \hline
\end{tabular}
\end{center}

Now let's guess what the translations are at each of the periods.  The
following is a table of common characters in each of the 11 decimations
of period 11, organized by the numbers of their appearances.

\begin{center}
\begin{tabular}{c|c|c|c|c|c|}
 $i$ &  9  &  8  &  7  &   6         &   5  \\ \hline
  1  & \hbox{\hspace{10mm}}
     & \hbox{\hspace{10mm}}
     & \hbox{\hspace{10mm}}
     & \tS,\tW,\tZ
     &  \tV \\ \hline
  2  &     &     &     &     \tL     &  \tA \\ \hline
  3  &     &     &     &     \tF     &  \tT \\ \hline
  4  &     &     & \tD &     \tO     &  \tR \\ \hline
  5  &     &     & \tL &             & \tI,\tW \\ \hline
  6  & \tW &     &     &             &  \tL \\ \hline
  7  & \tT &     &     &     \tH     &  \tW \\ \hline
  8  &     &     &     & \tI,\tS,\tX &  \tE \\ \hline
  9  &     &     & \tE &             &  \tH \\ \hline
 10  &     &     & \tZ &             & \tE,\tY \\ \hline
 11  &     &     & \tI
     & \hbox{\hspace{10mm}}
     & \hbox{\hspace{10mm}} \\ \hline
\end{tabular}
\end{center}

These characters are not themselves the characters in the key, but
if we assume that one of these frequently occurring characters is the
image of {\tt E}, then we can make a guess at the key.  The table
below gives the enciphering characters which take the corresponding
character in the previous table to {\tt E}.

\begin{center}
\begin{tabular}{c|c|c|c|c|c|}
 $i$ &  9  &  8  &  7  &   6         &   5  \\ \hline
  1  & \hbox{\hspace{10mm}}
     & \hbox{\hspace{10mm}}
     & \hbox{\hspace{10mm}}
     & \tM,\tI,\tF
     &  \tJ \\ \hline
  2  &     &     &     &     \tT     &  \tE \\ \hline
  3  &     &     &     &     \tZ     &  \tL \\ \hline
  4  &     &     & \tB &     \tQ     &  \tN \\ \hline
  5  &     &     & \tT &             & \tW,\tI \\ \hline
  6  & \tI &     &     &             &  \tT \\ \hline
  7  & \tL &     &     &     \tX     &  \tI \\ \hline
  8  &     &     &     & \tW,\tM,\tH &  \tA \\ \hline
  9  &     &     & \tA &             &  \tX \\ \hline
 10  &     &     & \tF &             & \tA,\tG \\ \hline
 11  &     &     & \tW
     & \hbox{\hspace{10mm}}
     & \hbox{\hspace{10mm}} \\ \hline
\end{tabular}
\end{center}

Checking possible keys, the partial key {\tt I****IL*A*W} gives the
following text which is suggestive of English:

\begin{center}
\begin{tabular}{rcccc}
   &         1         &           2       &          3        &          4       \\
 1 & {\tt W****OS*I*I} & {\tt N****ND*M*N} & {\tt E****BE*T*E} & {\tt E****LL*H*D} \\
 2 & {\tt A****YV*E*T} & {\tt H****UN*E*P} & {\tt E****BU*W*E} & {\tt N****EP*N*R} \\
 3 & {\tt E****HE*L*O} & {\tt K****EE*N*D} & {\tt A****BR*G*T} & {\tt A****IG*T*N} \\
 4 & {\tt D****IR*C*E} & {\tt D****TH*U*H} & {\tt O****AD*W*H} & {\tt A****DO*H*A} \\
 5 & {\tt K****GH*H*W} & {\tt W****TH*S*A} & {\tt D****OR*F*R} & {\tt M****YS*O*T} \\
 6 & {\tt O****LE*R*A} & {\tt Y****TH*M*C} & {\tt H****RE*L*G} & {\tt H****NT*U*S} \\
 7 & {\tt E****EY*S*H} & {\tt Y****ES*I*E} & {\tt S****WW*U*D} & {\tt I****IN*E*E} \\
 8 & {\tt S****ES*E*M} & {\tt A****LO*K*N} & {\tt G****EE*N*H} & {\tt E****NG*A*W} \\
 9 & {\tt H****DE*D*I} & {\tt G****YF*I*I} & {\tt M****EC*S*A} & {\tt D****OU*H*E} \\
10 & {\tt A****EE*O*S} & {\tt I****ES*E*E} & {\tt S****ST*Y*L} & {\tt L****AR*N*G} \\
11 & {\tt H****SE*T*L} & {\tt L****TH*E*N} & {\tt D****TS*R*G} & {\tt H****SW*E*D} \\
12 & {\tt R****DO*H*W} & {\tt T****E}\mbox{\hspace{11mm}}
\end{tabular}
\end{center}

\section{Cryptanalysis of Transposition Ciphers}

A transposition cipher can easily be recognized by an analysis of character frequencies.
Iterating transposition ciphers can greatly increase security, but as with substitution
ciphers, almost all such ciphers can be broken.  Although many modern cryptosystems
incorporate transposition ciphers, the operation on large blocks has the disadvantage
of requiring a lot of memory.

\section{Statistical Measures}

So far we have focused on Vigen\`ere ciphers, and their reduction to monoalphabetic
substitutions.  Here we show how to use Sage to complete the final step of breaking
these ciphers.  Recall that the reduction to monoalphabetic substitution is done by
the process of {\em decimation}, by which we lose all 2-character frequency structure
of the language.  A more sophisticated approach will be necessary for breaking more
complex ciphers.

\noindent{\bf Correlation}.
We first introduce the concept of correlation of two functions.
Let $\rX$ and $\rY$ be discrete random variables on a space $\Omega$ of $n$ symbols,
with values $(x_1, x_2, \dots, x_n)$ and $(y_1, y_2,\dots, y_n)$, respectively.
For simplicity we assume that all $n$ symbols of $\Omega$ occur with equal
likelihood.  We define the correlation of the two sequences to be
$$
{\rm Corr}(\rX,\rY) = \frac{\sum_{i=1}^n (x_i-\mu(\rX))(y_i-\mu(\rY))}
                       {\sigma(\rX) \sigma(\rY)}
$$
and where $\mu(\rX)$ and $\mu(\rY)$ are the respective {\em means}
of $\rX$ and $\rY$:
$$
\mu(\rX) = \frac{1}{n}\sum_{i=1}^n x_i, \quad
\mu(\rY) = \frac{1}{n}\sum_{i=1}^n y_i,
$$
and the terms in the denominators are:
$$
\sigma(\rX) = \Big(\sum_{i=1}^n (x_i-\mu(\rX))^2 \Big)^{1/2}, \quad
\sigma(\rY) = \Big(\sum_{i=1}^n (y_i-\mu(\rY))^2 \Big)^{1/2},
$$
called the {\em standard deviations} of $\rX$ and $\rY$. The correlation
of two sequences will be a real number between $1$ and $-1$, which measures
the linear relation between two sequences.  When the random variables $\rX$
and $\rY$ are probability functions, the means each reduce to $1/n$ (on a
probability space $\Omega$ with equal probabilities).

\section*{Exercises}

\input{exercises/ElementaryCryptanalysis}
